package com.adamjwh.pratice.offer;

/**
 * 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
 */
public class PrintMinNum {
    private static String str = "";
    private static String min;

    public String PrintMinNumber(int [] numbers) {
        if (numbers == null || numbers.length <= 0) {
            return "";
        }

        min = "";
        for(int i=0; i<numbers.length; i++) {
            min += numbers[i];
        }

        allSort(numbers, 0, numbers.length-1);

        return String.valueOf(min);
    }

    private static void allSort(int[] arr, int begin, int end) {
        if(begin == end) {
            for(int i=0; i<arr.length; i++) {
                str += arr[i];
            }

            if(min.compareTo(str) > 0) {
                min = str;
            }

            str = "";
            return ;
        }

        for (int i=begin; i<=end; i++) {
            swap(arr, begin, i);
            allSort(arr, begin+1, end);
            swap(arr, begin, i);
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}
